package com.sheng.leetcode.year2022.swordfingeroffer.day15;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/09/13
 *<p>
 * 剑指 Offer 34. 二叉树中和为某一值的路径<p>
 *<p>
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。<p>
 * 叶子节点 是指没有子节点的节点。<p>
 *<p>
 * 示例 1：<p>
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22<p>
 * 输出：[[5,4,11,2],[5,8,4,5]]<p>
 * <p>
 * 示例 2：<p>
 * 输入：root = [1,2,3], targetSum = 5<p>
 * 输出：[]<p>
 * <p>
 * 示例 3：<p>
 * 输入：root = [1,2], targetSum = 0<p>
 * 输出：[]<p>
 *<p>
 * 提示：<p>
 *<p>
 * 树中节点总数在范围 [0, 5000] 内<p>
 * -1000 <= Node.val <= 1000<p>
 * -1000 <= targetSum <= 1000<p>
 * 注意：本题与主站 113题相同：<a href="https://leetcode-cn.com/problems/path-sum-ii/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0034 {

    @Test
    public void test01() {
//        TreeNode root = new TreeNode(5);
//        TreeNode left = new TreeNode(4);
//        TreeNode left1 = new TreeNode(11);
//        left1.left = new TreeNode(7);
//        left1.right = new TreeNode(2);
//        left.left = left1;
//        TreeNode right = new TreeNode(8);
//        right.left = new TreeNode(13);
//        TreeNode right1 = new TreeNode(4);
//        right1.left = new TreeNode(5);
//        right1.right = new TreeNode(1);
//        right.right = right1;
//        root.left = left;
//        root.right = right;
//        int target = 22;

//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);
//        int target = 5;

//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        int target = 1;

        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(4);
        left.right = new TreeNode(3);
        right.right = new TreeNode(5);
        root.left = left;
        root.right = right;
        int target = 6;
        System.out.println(new Solution().pathSum(root, target));
    }
}
class Solution {
    int t;
    List<List<Integer>> lists;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        lists = new ArrayList<>();
        t = target;
        dfs(new ArrayList<>(), root, 0);
        return lists;
    }

    public void dfs(List<Integer> list, TreeNode node, int sum) {
        if (node == null) {
            return;
        }
        list.add(node.val);
        // 如果刚好遍历到子节点，并且加起来值等于目标值
        if (sum + node.val == t && node.left == null && node.right == null) {
            lists.add(new ArrayList<>(list));
        }
        dfs(list, node.left, sum + node.val);
        dfs(list, node.right, sum + node.val);
        list.remove(list.size() - 1);
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
